package 代码随想2._5双指针法;

/**
 * @author XXX
 * @date 2024-01-17 15:51
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.cn/problems/4sum/description/
 */
public class _10四数之和 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);

        for (int i=0;i<nums.length;i++){
            if (nums[i] > 0 && nums[i] > target)
                return res;
            if (i>0 && nums[i]==nums[i-1])
                continue;

            for(int j=i+1; j<nums.length;j++) {
                if (j > i + 1 && nums[j - 1] == nums[j])
                    continue;

                int left = j+1;
                int right = nums.length - 1;
                while (right>left){
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum > target)
                        right--;
                    else if(sum < target)
                        left++;
                    else {
                        res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));

                        while (left<right && nums[right] == nums[right-1]) right--;
                        while (left < right && nums[left] == nums[left+1]) left++;

                        right--;
                        left++;
                    }
                }
            }
        }
        return res;
    }
}
